SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Lloyd's algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Lloyd's algorithm</span></span>

</h1>

</header>

<p>In <a href="Electrical_engineering" title="Electrical engineering">electrical engineering</a> and <a href="Computer_science" title="Computer science">computer science</a>, <b>Lloyd's algorithm</b>, also known as <b>Voronoi iteration</b> or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of <a href="Euclidean_space" title="Euclidean space">Euclidean spaces</a> and partitions of these subsets into well-shaped and uniformly sized convex cells.<sup id="cite_ref-l82_1-0" class="reference"><a href="#cite_note-l82-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Like the closely related <a href="K-means_clustering" title="K-means clustering"><i>k</i>-means clustering</a> algorithm, it repeatedly finds the <a href="Centroid" title="Centroid">centroid</a> of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in <a href="Voronoi_diagram" title="Voronoi diagram">Voronoi diagrams</a>.

</p><p>Although the algorithm may be applied most directly to the <a href="Euclidean_plane" title="Euclidean plane">Euclidean plane</a>, similar algorithms may also be applied to higher-dimensional spaces or to spaces with other <a href="Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a> metrics. Lloyd's algorithm can be used to construct close approximations to <a href="Centroidal_Voronoi_tessellation" title="Centroidal Voronoi tessellation">centroidal Voronoi tessellations</a> of the input,<sup id="cite_ref-dfg99_2-0" class="reference"><a href="#cite_note-dfg99-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> which can be used for <a href="Quantization_(signal_processing)" title="Quantization (signal processing)">quantization</a>, <a href="Dithering" class="mw-redirect" title="Dithering">dithering</a>, and <a href="Stippling" title="Stippling">stippling</a>. Other applications of Lloyd's algorithm include smoothing of <a href="Triangle_mesh" title="Triangle mesh">triangle meshes</a> in the <a href="Finite_element_method" title="Finite element method">finite element method</a>.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .tmulti .multiimageinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;text-align:center}.mw-parser-output .tmulti .tsingle .thumbcaption{text-align:left}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="thumb tmulti tleft"><div class="thumbinner multiimageinner" style="width:816px;max-width:816px"><div class="trow"><div class="theader" style="text-align:left">Example of Lloyd's algorithm. The Voronoi diagram of the current site positions (red) at each iteration is shown. The gray circles denote the centroids of the Voronoi cells.</div></div><div class="trow"><div class="tsingle" style="width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">Iteration 1</div></div><div class="tsingle" style="width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">Iteration 2</div></div><div class="tsingle" style="width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">Iteration 3</div></div><div class="tsingle" style="width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">Iteration 15</div></div></div><div class="trow" style="display:flex"><div class="thumbcaption">In the last image, the sites are very near the centroids of the Voronoi cells. A centroidal Voronoi tessellation has been found.</div></div></div></div>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>The algorithm was first proposed by Stuart P. Lloyd of <a href="Bell_Labs" title="Bell Labs">Bell Labs</a> in 1957 as a technique for <a href="Pulse-code_modulation" title="Pulse-code modulation">pulse-code modulation</a>. Lloyd's work became widely circulated but remained unpublished until 1982.<sup id="cite_ref-l82_1-1" class="reference"><a href="#cite_note-l82-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> A similar algorithm was developed independently by Joel Max and published in 1960,<sup id="cite_ref-m60_3-0" class="reference"><a href="#cite_note-m60-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> which is why the algorithm is sometimes referred as the Lloyd-Max algorithm.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm_description">Algorithm description</h2></div>

<p>Lloyd's algorithm starts by an initial placement of some number <i>k</i> of point sites in the input domain. In mesh-smoothing applications, these would be the vertices of the mesh to be smoothed; in other applications they may be placed at random or by intersecting a uniform triangular mesh of the appropriate size with the input domain.

</p><p>It then repeatedly executes the following relaxation step:

</p>

<ul><li>The <a href="Voronoi_diagram" title="Voronoi diagram">Voronoi diagram</a> of the <i>k</i> sites is computed.</li>

<li>Each cell of the Voronoi diagram is integrated, and the centroid is computed.</li>

<li>Each site is then moved to the centroid of its Voronoi cell.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Integration_and_centroid_computation">Integration and centroid computation</h2></div>

<p>Because Voronoi diagram construction algorithms can be highly non-trivial, especially for inputs of dimension higher than two, the steps of calculating this diagram and finding the exact centroids of its cells may be replaced by an approximation.

</p>

<div class="mw-heading mw-heading3"><h3 id="Approximation">Approximation</h3></div>

<p>A common simplification is to employ a suitable discretization of space like a fine pixel-grid, e.g. the texture <a href="Z-buffering" title="Z-buffering">buffer</a> in graphics hardware. Cells are materialized as pixels, labeled with their corresponding site-ID. A cell's new center is approximated by averaging the positions of all pixels assigned with the same label.

Alternatively, <a href="Monte_Carlo_methods" class="mw-redirect" title="Monte Carlo methods">Monte Carlo methods</a> may be used, in which random sample points are generated according to some fixed underlying probability distribution, assigned to the closest site, and averaged to approximate the centroid for each site.

</p>

<div class="mw-heading mw-heading3"><h3 id="Exact_computation">Exact computation</h3></div>

<p>Although embedding in other spaces is also possible, this elaboration assumes <a href="Euclidean_distance" title="Euclidean distance">Euclidean space</a> using the <a href="Lp_space" title="Lp space"><i>L<sup>2</sup></i> norm</a> and discusses the two most relevant scenarios, which are two, and respectively three dimensions.

</p><p>Since a Voronoi cell is of convex shape and always encloses its site, there exist trivial decompositions into easy integratable simplices:

</p>

<ul><li>In two dimensions, the edges of the polygonal cell are connected with its site, creating an umbrella-shaped set of triangles.</li>

<li>In three dimensions, the cell is enclosed by several planar polygons which have to be triangulated first:

<ul><li>Compute a center for the polygon face, e.g. the average of all its vertices.</li>

<li>Connecting the vertices of a polygon face with its center gives a planar umbrella-shaped triangulation.</li>

<li>Trivially, a set of <a href="Tetrahedron" title="Tetrahedron">tetrahedra</a> is obtained by connecting triangles of the cell's hull with the cell's site.</li></ul></li></ul>

<p>Integration of a cell and computation of its <a href="Centroid" title="Centroid">centroid</a> (<a href="Center_of_mass" title="Center of mass">center of mass</a>) is now given as a weighted combination of its simplices' centroids (in the following called <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mathbf {c} _{i}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mathbf {c} _{i}}</annotation>

</semantics>

</math></span><img src="./deedcdc9abd90ad05e7123a7238767bf1273ce62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.988ex; height:2.009ex;" alt="{\textstyle \mathbf {c} _{i}}" loading="lazy"></span>).

</p>

<ul><li>Two dimensions:

<ul><li>For a triangle the centroid can be easily computed, e.g. using <a href="Centroid#By_geometric_decomposition" title="Centroid">cartesian coordinates</a>.</li>

<li>Weighting computes as simplex-to-cell <b>area</b> ratios.</li></ul></li>

<li>Three dimensions:

<ul><li>The <a href="Tetrahedron#Centroid" title="Tetrahedron">centroid of a tetrahedron</a> is found as the intersection of three bisector planes and can be expressed as a matrix-vector product.</li>

<li>Weighting computes as simplex-to-cell <b>volume</b> ratios.</li></ul></li></ul>

<p>For a 2D cell with <span class="texhtml"><i>n</i></span> triangular simplices and an accumulated area <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle A_{C}=\sum _{i=0}^{n}a_{i}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle A_{C}=\sum _{i=0}^{n}a_{i}}</annotation>

</semantics>

</math></span><img src="./14e59ba6f02cd8f4f0bd088285fd3c366b6999e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.093ex; height:3.176ex;" alt="{\textstyle A_{C}=\sum _{i=0}^{n}a_{i}}" loading="lazy"></span> (where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle a_{i}}</annotation>

</semantics>

</math></span><img src="./b0affb4afce7ef19e623f75f2f8e70e1f6e5616c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\textstyle a_{i}}" loading="lazy"></span> is the <a href="Triangle#Computing_the_area_of_a_triangle" title="Triangle">area of a triangle</a> simplex), the new cell centroid computes as:

</p>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C={\frac {1}{A_{C}}}\sum _{i=0}^{n}\mathbf {c} _{i}a_{i}}</annotation>

</semantics>

</math></span><img src="./f1f3eff16e34f8bb56781fe99a1cbdd48326676f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.072ex; height:6.843ex;" alt="{\displaystyle C={\frac {1}{A_{C}}}\sum _{i=0}^{n}\mathbf {c} _{i}a_{i}}" loading="lazy"></span></dd></dl>

<p>Analogously, for a 3D cell with a volume of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle V_{C}=\sum _{i=0}^{n}v_{i}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle V_{C}=\sum _{i=0}^{n}v_{i}}</annotation>

</semantics>

</math></span><img src="./7ddf2370b9fafc4fc5e02b3adb2f9d997ec931bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.603ex; height:3.176ex;" alt="{\textstyle V_{C}=\sum _{i=0}^{n}v_{i}}" loading="lazy"></span> (where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle v_{i}}</annotation>

</semantics>

</math></span><img src="./6126ad3375b4bd895f169ef76fc2946672ec8d17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\textstyle v_{i}}" loading="lazy"></span> is the <a href="Tetrahedron#Volume" title="Tetrahedron">volume of a tetrahedron</a> simplex), the centroid computes as:

</p>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C={\frac {1}{V_{C}}}\sum _{i=0}^{n}\mathbf {c} _{i}v_{i}}</annotation>

</semantics>

</math></span><img src="./682277fdc94ac476bc9abc7b439f21d2405a9ba7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:16.582ex; height:6.843ex;" alt="{\displaystyle C={\frac {1}{V_{C}}}\sum _{i=0}^{n}\mathbf {c} _{i}v_{i}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Convergence">Convergence</h2></div>

<p>Each time a relaxation step is performed, the points are left in a slightly more even distribution: closely spaced points move farther apart, and widely spaced points move closer together. In one dimension, this algorithm has been shown to converge to a centroidal Voronoi diagram, also named a <a href="Centroidal_Voronoi_tessellation" title="Centroidal Voronoi tessellation">centroidal Voronoi tessellation</a>.<sup id="cite_ref-dej06_4-0" class="reference"><a href="#cite_note-dej06-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> In higher dimensions, some slightly weaker convergence results are known.<sup id="cite_ref-sg86_5-0" class="reference"><a href="#cite_note-sg86-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-ejr09_6-0" class="reference"><a href="#cite_note-ejr09-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p><p>The algorithm converges slowly or, due to limitations in numerical precision, may not converge. Therefore, real-world applications of Lloyd's algorithm typically stop once the distribution is "good enough." One common termination criterion is to stop when the maximum distance moved by any site in an iteration falls below a preset threshold. Convergence can be accelerated by over-relaxing the points, which is done by moving each point <b>ω</b> times the distance to the center of mass, typically using a value slightly less than 2 for <b>ω</b>.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>Lloyd's method was originally used for scalar quantization, but it is clear that the method extends for <a href="Vector_quantization" title="Vector quantization">vector quantization</a> as well. As such, it is extensively used in <a href="Data_compression" title="Data compression">data compression</a> techniques in <a href="Information_theory" title="Information theory">information theory</a>. Lloyd's method is used in computer graphics because the resulting distribution has <a href="Blue_noise" class="mw-redirect" title="Blue noise">blue noise</a> characteristics (see also <a href="Colors_of_noise" title="Colors of noise">Colors of noise</a>), meaning there are few low-frequency components that could be interpreted as artifacts. It is particularly well-suited to picking sample positions for <a href="Dithering" class="mw-redirect" title="Dithering">dithering</a>. Lloyd's algorithm is also used to generate dot drawings in the style of <a href="Stippling" title="Stippling">stippling</a>.<sup id="cite_ref-dhos00_8-0" class="reference"><a href="#cite_note-dhos00-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> In this application, the centroids can be weighted based on a reference image to produce stipple illustrations matching an input image.<sup id="cite_ref-s02_9-0" class="reference"><a href="#cite_note-s02-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p><p>In the <a href="Finite_element_method" title="Finite element method">finite element method</a>, an input domain with a <a href="Complex_geometry" title="Complex geometry">complex geometry</a> is partitioned into elements with simpler shapes; for instance, two-dimensional domains (either subsets of the Euclidean plane or surfaces in three dimensions) are often partitioned into triangles. It is important for the convergence of the finite element methods that these elements be well shaped; in the case of triangles, often elements that are nearly equilateral triangles are preferred. Lloyd's algorithm

can be used to smooth a mesh generated by some other algorithm, moving its vertices and changing the connection pattern among its elements in order to produce triangles that are more closely equilateral.<sup id="cite_ref-dg02_10-0" class="reference"><a href="#cite_note-dg02-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> These applications typically use a smaller number of iterations of Lloyd's algorithm, stopping it to convergence, in order to preserve other features of the mesh such as differences in element size in different parts of the mesh. In contrast to a different smoothing method, <a href="Laplacian_smoothing" title="Laplacian smoothing">Laplacian smoothing</a> (in which mesh vertices are moved to the average of their neighbors' positions), Lloyd's algorithm can change the topology of the mesh, leading to more nearly equilateral elements as well as avoiding the problems with tangling that can arise with Laplacian smoothing. However, Laplacian smoothing can be applied more generally to meshes with non-triangular elements.

</p>

<div class="mw-heading mw-heading2"><h2 id="Different_distances">Different distances</h2></div>

<p>Lloyd's algorithm is usually used in a <a href="Euclidean_space" title="Euclidean space">Euclidean space</a>. The Euclidean distance plays two roles in the algorithm: it is used to define the Voronoi cells, but it also corresponds to the choice of the centroid as the representative point of each cell, since the centroid is the point that minimizes the average squared Euclidean distance to the points in its cell. Alternative distances, and alternative central points than the centroid, may be used instead. For example, <a href="#CITEREFHausner2001">Hausner (2001)</a> used a variant of the <a href="Manhattan_metric" class="mw-redirect" title="Manhattan metric">Manhattan metric</a> (with locally varying orientations) to find a tiling of an image by approximately square tiles whose orientation aligns with features of an image, which he used to simulate the construction of tiled <a href="Mosaic" title="Mosaic">mosaics</a>.<sup id="cite_ref-h01_11-0" class="reference"><a href="#cite_note-h01-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> In this application, despite varying the metric, Hausner continued to use centroids as the representative points of their Voronoi cells. However, for metrics that differ more significantly from Euclidean, it may be appropriate to choose the minimizer of average squared distance as the representative point, in place of the centroid.<sup id="cite_ref-dew10_12-0" class="reference"><a href="#cite_note-dew10-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li>The <a href="Linde%E2%80%93Buzo%E2%80%93Gray_algorithm" title="Linde–Buzo–Gray algorithm">Linde–Buzo–Gray algorithm</a>, a generalization of this algorithm for vector quantization</li>

<li><a href="Farthest-first_traversal" title="Farthest-first traversal">Farthest-first traversal</a>, a different method for generating evenly spaced points in geometric spaces</li>

<li><a href="Mean_shift" title="Mean shift">Mean shift</a>, a related method for finding maxima of a density function</li>

<li><a href="K-means%2B%2B" title="K-means++">K-means++</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLloyd1982" class="citation cs2">Lloyd, Stuart P. (1982), "Least squares quantization in PCM", <i><a href="IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a></i>, <b>28</b> (2): <span class="nowrap">129–</span>137, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1982.1056489">10.1109/TIT.1982.1056489</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10833328">10833328</a></cite>.</span>

</li>

<li id="cite_note-dfg99-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-dfg99_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFDuFaberGunzburger1999" class="citation cs2"><a href="Qiang_Du" title="Qiang Du">Du, Qiang</a>; Faber, Vance; Gunzburger, Max (1999), "Centroidal Voronoi tessellations: applications and algorithms", <i>SIAM Review</i>, <b>41</b> (4): <span class="nowrap">637–</span>676, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1999SIAMR..41..637D">1999SIAMR..41..637D</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0036144599352836">10.1137/S0036144599352836</a></cite>.</span>

</li>

<li id="cite_note-m60-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-m60_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFMax1960" class="citation cs2">Max, Joel (1960), "Quantizing for minimum distortion", <i><a href="IRE_Transactions_on_Information_Theory" class="mw-redirect" title="IRE Transactions on Information Theory">IRE Transactions on Information Theory</a></i>, <b>6</b> (1): <span class="nowrap">7–</span>12, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1960.1057548">10.1109/TIT.1960.1057548</a></cite>.</span>

</li>

<li id="cite_note-dej06-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-dej06_4-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFDuEmelianenkoJu2006" class="citation cs2"><a href="Qiang_Du" title="Qiang Du">Du, Qiang</a>; <a href="Maria_Emelianenko" title="Maria Emelianenko">Emelianenko, Maria</a>; Ju, Lili (2006), "Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations", <i>SIAM Journal on Numerical Analysis</i>, <b>44</b>: <span class="nowrap">102–</span>119, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.591.9903">10.1.1.591.9903</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F040617364">10.1137/040617364</a></cite>.</span>

</li>

<li id="cite_note-sg86-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-sg86_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFSabinGray1986" class="citation cs2">Sabin, M. J.; Gray, R. M. (1986), "Global convergence and empirical consistency of the generalized Lloyd algorithm", <i><a href="IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a></i>, <b>32</b> (2): <span class="nowrap">148–</span>155, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1986.1057168">10.1109/TIT.1986.1057168</a></cite>.</span>

</li>

<li id="cite_note-ejr09-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-ejr09_6-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFEmelianenkoJuRand2009" class="citation cs2">Emelianenko, Maria; Ju, Lili; Rand, Alexander (2009), "Nondegeneracy and Weak Global Convergence of the Lloyd Algorithm in <b>R</b><sup>d</sup>", <i>SIAM Journal on Numerical Analysis</i>, <b>46</b>: <span class="nowrap">1423–</span>1441, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F070691334">10.1137/070691334</a></cite>.</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">Xiao, Xiao. "Over-relaxation Lloyd method for computing centroidal Voronoi tessellations." (2010).</span>

</li>

<li id="cite_note-dhos00-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-dhos00_8-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFDeussenHillervan_OverveldStrothotte2000" class="citation cs2">Deussen, Oliver; Hiller, Stefan; van Overveld, Cornelius; Strothotte, Thomas (2000), "Floating points: a method for computing stipple drawings", <i>Computer Graphics Forum</i>, <b>19</b> (3): <span class="nowrap">41–</span>50, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.233.5810">10.1.1.233.5810</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2F1467-8659.00396">10.1111/1467-8659.00396</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:142991">142991</a>, Proceedings of <a href="Eurographics" title="Eurographics">Eurographics</a></cite>.</span>

</li>

<li id="cite_note-s02-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-s02_9-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFSecord2002" class="citation cs2">Secord, Adrian (2002), "Weighted Voronoi stippling", <i>Proceedings of the Symposium on Non-Photorealistic Animation and Rendering (NPAR)</i>, <a href="ACM_SIGGRAPH" title="ACM SIGGRAPH">ACM SIGGRAPH</a>, pp. <span class="nowrap">37–</span>43, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F508530.508537">10.1145/508530.508537</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-58113-494-0</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12153589">12153589</a></cite>.</span>

</li>

<li id="cite_note-dg02-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-dg02_10-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFDuGunzburger2002" class="citation cs2"><a href="Qiang_Du" title="Qiang Du">Du, Qiang</a>; Gunzburger, Max (2002), "Grid generation and optimization based on centroidal Voronoi tessellations", <i>Applied Mathematics and Computation</i>, <b>133</b> (<span class="nowrap">2–</span>3): <span class="nowrap">591–</span>607, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.324.5020">10.1.1.324.5020</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0096-3003%2801%2900260-0">10.1016/S0096-3003(01)00260-0</a></cite>.</span>

</li>

<li id="cite_note-h01-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-h01_11-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFHausner2001" class="citation cs2">Hausner, Alejo (2001), "Simulating decorative mosaics", <i>Proceedings of the 28th annual conference on Computer graphics and interactive techniques</i>, <a href="ACM_SIGGRAPH" title="ACM SIGGRAPH">ACM SIGGRAPH</a>, pp. <span class="nowrap">573–</span>580, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F383259.383327">10.1145/383259.383327</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-58113-374-X</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7188986">7188986</a></cite>.</span>

</li>

<li id="cite_note-dew10-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-dew10_12-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFDickersonEppsteinWortman2010" class="citation cs2"><a href="Matthew_T._Dickerson" title="Matthew T. Dickerson">Dickerson, Matthew T.</a>; <a href="David_Eppstein" title="David Eppstein">Eppstein, David</a>; Wortman, Kevin A. (2010), "Planar Voronoi diagrams for sums of convex functions, smoothed distance and dilation", <i>Proc. 7th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2010)</i>, pp. <span class="nowrap">13–</span>22, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0812.0607">0812.0607</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FISVD.2010.12">10.1109/ISVD.2010.12</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4244-7606-0</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15971504">15971504</a></cite>.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://demogng.de/js/demogng.html?model=LBG&showAutoRestart&showVoronoi">DemoGNG.js</a> Graphical Javascript simulator for LBG algorithm and other models, includes display of Voronoi regions</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-29" href="https://en.wikipedia.org/wiki/?title=Lloyd's_algorithm&oldid=1287965390">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>